package com.dmall.play.interview.chapter08;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Leetcode131V2 {

    private final List<List<String>> ans = new ArrayList<>();

    public List<List<String>> partition(String s) {
        if (s == null || "".equalsIgnoreCase(s)) {
            return ans;
        }
        Deque<String> stack = new ArrayDeque<>();
        findPalindrome(s, 0, s.length(), stack);
        return ans;
    }

    private void findPalindrome(String s, int start, int len, Deque<String> stack) {
        if (start == len) {
            ans.add(new ArrayList<>(stack));
            return;
        }

        for (int i = start; i < len; i++) {
            if (isPalindrome(s, start, i)) {
                stack.add(s.substring(start, i + 1));
                findPalindrome(s, i + 1, len, stack);
                stack.removeLast();
            }
        }
    }

    private boolean isPalindrome(String s, int start, int end) {
        boolean flag = true;
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                flag = false;
                break;
            }
            start ++;
            end --;
        }
        return flag;
    }

    public static void main(String[] args) {
        Leetcode131V2 leetcode131 = new Leetcode131V2();
        List<List<String>> res = leetcode131.partition("aab");
        System.out.println(res);
    }
}
